package tree;

import array.ListNode;
public class ConvertSortedListToBinarySearchTree109 {

    public TreeNode sortedListToBST(ListNode head) {
//        ListNode idle = new ListNode();
//        idle.next = head;
        return buildTree(head,null);

    }


    private TreeNode buildTree(ListNode begin, ListNode end) {
        if(begin==end){
            return null;
        }
        ListNode mid = getMid(begin,end);
        TreeNode left = buildTree(begin,mid);
        TreeNode right = buildTree(mid.next,end);
        TreeNode root = new TreeNode(mid.val);
        root.left = left;
        root.right = right;
        return root;
    }


    private ListNode getMid(ListNode begin,ListNode end){
        if(begin==null){
            return begin;
        }
        ListNode quick=begin;
        ListNode slow = begin;
        while (quick!=end&&quick.next!=end){
            quick=quick.next.next;
            slow = slow.next;
        }
        return slow;
    }
//        public TreeNode sortedListToBST(ListNode head) {
////        ListNode idle = new ListNode();
////        idle.next = head;
//        ListNode midNode = getMidNode(head);
//        if (midNode != null) {
//            ListNode new_head = midNode.next;
//            midNode.next = null;
//            if (new_head != null) {
//                TreeNode root = new TreeNode(new_head.val);
//                root.left = sortedListToBST(head);
//                root.right = sortedListToBST(new_head.next);
//                return root;
//            }
//
//        }
//        return null;
//    }
//
//
//    private ListNode getMidNode(ListNode head) {
//        ListNode idle = new ListNode();
//        idle.next = head;
//        ListNode quick = idle;
//        ListNode slow = idle;
//        while (quick != null && quick.next != null) {
//            quick = quick.next.next;
//            slow = slow.next;
//        }
//        return slow;
//    }
}
